package array;

/**
 * 给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。
 * 对于每个查询 queries[i]：
 * 在 nums 的下标范围 [li, ri] 内选择一个下标 子集。
 * 将选中的每个下标对应的元素值减 1。
 * 零数组 是指所有元素都等于 0 的数组。
 * 如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。
 * <p>
 * 示例 1：
 * 输入： nums = [1,0,1], queries = [[0,2]]
 * 输出： true
 * 解释：
 * 对于 i = 0：
 * 选择下标子集 [0, 2] 并将这些下标处的值减 1。
 * 数组将变为 [0, 0, 0]，这是一个零数组。
 * <p>
 * 示例 2：
 * 输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]
 * 输出： false
 * 解释：
 * 对于 i = 0：
 * 选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。
 * 数组将变为 [4, 2, 1, 0]。
 * 对于 i = 1：
 * 选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。
 * 数组将变为 [3, 1, 0, 0]，这不是一个零数组。
 *
 * @author Jisheng Huang
 * @version 20250520
 */
public class ZeroArrayTransI_3355 {

    /**
     * 题意可以转换成：
     * 把 [li ,ri] 中的元素都减一，最终数组中的所有元素是否都 ≤0？
     * 如果所有元素都 ≤0，那么我们可以撤销一部分元素的减一，使其调整为 0，从而满足原始题意的要求。
     *
     * @param nums    the given integer array
     * @param queries the given query interval array
     * @return whether you can make the array zero
     */
    public static boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];

        for (int[] q : queries) {
            // Add 1 to the number in the interval
            ++diff[q[0]];
            --diff[q[1] + 1];
        }

        int sumD = 0;

        for (int i = 0; i < n; ++i) {
            sumD += diff[i];

            // 此时 sumD 表示 nums[i] 要减掉多少
            if (nums[i] > sumD) { // nums[i] 无法变成 0
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, 1};
        int[][] queries = {{0, 2}};
        System.out.println(isZeroArray(nums, queries));

        nums = new int[]{4, 3, 2, 1};
        queries = new int[][]{{1, 3}, {0, 2}};
        System.out.println(isZeroArray(nums, queries));
    }
}
